package algorithm_demo.sort;

import java.util.Arrays;

/**
 * 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 (Divide and Conquer) 的一个非常典型的应用。
 * 归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 - 路归并。
 * 和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间
 * <p>
 * 算法步骤
 * 归并排序算法是一个递归过程，边界条件为当输入序列仅有一个元素时，直接返回，具体过程如下：
 * 1. 如果输入内只有一个元素，则直接返回，否则将长度为 n 的输入序列分成两个长度为 n/2 的子序列；
 * 2. 分别对这两个子序列进行归并排序，使子序列变为有序状态；
 * 3. 设定两个指针，分别指向两个已经排序子序列的起始位置；
 * 4. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；
 * 5. 重复步骤 3 ~4 直到某一指针达到序列尾；
 * 6. 将另一序列剩下的所有元素直接复制到合并序列尾。
 * <p>
 * 算法分析
 * 稳定性：稳定
 * 时间复杂度 ：最佳：O(nlogn)， 最差：O(nlogn)， 平均：O(nlogn)
 * 空间复杂度 ：O(n)
 * @author Api
 * @date 2022/11/19 14:01
 */
public class MergeSort5 {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 45, 2, 1, 34, 4, 2, 2, 4, 2};//给定一个数组
        int[] ints = sortArray(arr); //的带排序后的数组
        System.out.println(Arrays.toString(ints));//打印输出得到数组
    }


    private static int[] sortArray(int[] arr) {
        int len = arr.length;
        int[] temp = new int[len];
        mergeSort(arr, 0, len - 1, temp);
        return arr;
    }

    /**
     * arr[left...right]进行归并排序
     *
     * @param arr   原数组
     * @param left  左边的索引
     * @param right 右边记录索引位置
     * @param temp
     */
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (right - left < 16) {//当拆分到数组长度小于16的时候，直接插入排序来提高代码运行速度
            insertionSort(arr, right, left);
            return;
        }
        int mid = left + ((right - left) >> 1);//找到下次要拆分的中间值
        mergeSort(arr, left, mid, temp);//记录树左边的
        mergeSort(arr, mid + 1, right, temp);//记录树右边的
        if (arr[mid] <= arr[mid + 1]) {
            //因为整数除法是向下取整，所以这里不会代写mid+1越界
            return;
        }
        //合并两个区间
        if (right + 1 - left >= 0) {
            //temp就是辅助列表，新列表的需要排序的值就是从辅助列表中拿到的
            System.arraycopy(arr, left, temp, left, right + 1 - left);
        }
        int i = left;
        int j = mid + 1;
        for (int k = left; k <= right; k++) {//k 就为当前要插入的位置
            if (i == mid + 1) {
                arr[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                arr[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
        }
    }

    /**
     * 插入排序
     */
    private static void insertionSort(int[] arr, int right, int left) {
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j > left; j--) {
                if (arr[j - 1] > temp) {
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            arr[j] = temp;
        }
    }
}
